package com.sicheng.algorithm.recursive;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/8/27 16:54
 */


public class WordSearch {
    public static void main(String[] args) {

        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'},
        };
        System.out.println(search(board, "ABCCEEECC", 0, 0, 0));
        // todo
        //可以写个方法，找到所有Word的入口
        //依次调用search，只要有一个入口完全匹配就返回true
    }

    /**
     * word search(二维数组中查找单词（匹配字符串）)
     * For example,
     * Given board =
     * <p>
     * [
     * ['A','B','C','E'],
     * ['S','F','C','S'],
     * ['A','D','E','E']
     * ]
     * word = "ABCCED", -> returns true,
     * word = "SEE", -> returns true,
     * word = "ABCB", -> returns false.
     * <p>
     * <p>
     * 从二维数组中找字符串是否存在，而且同一个元素不能重复使用。
     * 这是字符串匹配类型 题目，要记住方法。
     * 将二维数组简化成字符串，也就是字符串匹配了（依次遍历每个元素，将其当做开头，开始匹配）。
     */
    //  从入口处递归匹配，即Word的首字母处进入
    public static boolean search(char[][] board, String word, int i, int j, int n) {
        if (board != null && word != null && board.length > 0) {
            if (n == word.length())//递归的终点
                return true;
            //依次向上下左右四个方向进行匹配，失败则回溯继续匹配
            if (board[i][j] != word.charAt(n))//匹配失败，回溯
                return false;
            if (i > 0 && search(board, word, i - 1, j, n + 1))//向上匹配
                return true;
            if (i < board.length - 1 && search(board, word, i + 1, j, n + 1))//向下匹配
                return true;
            if (j > 0 && search(board, word, i, j - 1, n + 1))//向左匹配
                return true;
            else return j < board[0].length - 1 && search(board, word, i, j + 1, n + 1);//向右匹配
        }
        return false;
    }
}
